package com.hy;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:零钱兑换
 *
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 *
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 *
 * 你可以认为每种硬币的数量是无限的。
 *
 * author: Mr.Du
 * Date: 2023/11/17
 * Time: 19:24
 */
public class CoinChange {

    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        Arrays.fill(f, Integer.MAX_VALUE / 2); // 除 2 是防止下面 + 1 溢出
        f[0] = 0;
        for (int x : coins)
            for (int c = x; c <= amount; ++c)
                f[c] = Math.min(f[c], f[c - x] + 1);
        int ans = f[amount];
        return ans < Integer.MAX_VALUE / 2 ? ans : -1;
    }

    public int coinChange2(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        // dp[i]表示以凑够i所需的最少硬币个数
        for(int i = 1;i < amount + 1;i++){
            for(int j = 0;j < coins.length;j++){
                if( i >= coins[j] && dp[i-coins[j]] != amount + 1)
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        return dp[amount] == (amount + 1)? -1 : dp[amount];
    }

    private int[] coins;
    private int[][] memo;

    public int coinChange1(int[] coins, int amount) {
        this.coins = coins;
        int n = coins.length;
        memo = new int[n][amount + 1];
        for (int[] row : memo)
            Arrays.fill(row, -1); // -1 表示没有访问过
        int ans = dfs(n - 1, amount);
        return ans < Integer.MAX_VALUE / 2 ? ans : -1;
    }

    private int dfs(int i, int c) {
        if (i < 0) return c == 0 ? 0 : Integer.MAX_VALUE / 2; // 除 2 是防止下面 + 1 溢出
        if (memo[i][c] != -1) return memo[i][c];
        if (c < coins[i]) return memo[i][c] = dfs(i - 1, c);
        return memo[i][c] = Math.min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
    }

    /**
     * 使用动态规划解决硬币找零问题。
     * 给定不同面额的硬币 coins 和一个总金额 amount，编写一个函数返回可以凑成总金额所需的最少的硬币个数。
     * 如果无法凑成总金额，则返回 -1。
     *
     * @param coins 不同面额的硬币数组。
     * @param amount 总金额。
     * @return 返回可以凑成总金额所需的最少的硬币个数，如果无法凑成则返回 -1。
     */
    public int coinChange3(int[] coins, int amount) {
        int n = coins.length;
        // 创建动态规划数组，f[i][c] 表示使用前 i 种硬币凑成金额 c 所需的最少硬币数
        int[][] f = new int[n + 1][amount + 1];
        Arrays.fill(f[0], amount + 1);
        // 凑成金额为 0 所需的硬币数为 0
        f[0][0] = 0;

        // 动态规划遍历
        for (int i = 0; i < n; ++i) {
            for (int c = 0; c <= amount; ++c) {
                if (c < coins[i]) {
                    // 如果当前硬币面额大于当前金额，则无法使用该硬币，直接继承前一种情况的结果
                    f[i + 1][c] = f[i][c];
                } else {
                    // 否则，考虑使用当前硬币，取使用和不使用当前硬币两种情况中的较小值
                    f[i + 1][c] = Math.min(f[i][c], f[i + 1][c - coins[i]] + 1);
                }
            }
        }
        // 最终结果为使用所有硬币凑成总金额所需的最少硬币数
        int ans = f[n][amount];
        // 如果最终结果小于 amount + 1（初始时设置的较大值），则返回该结果，否则返回 -1，表示无法凑成总金额
        return ans < amount + 1 ? ans : -1;
    }


}
